1. Field of the Invention
The present invention pertains generally to the field of computer graphics. More particularly, the present invention pertains to coding of information representing an image of a three dimensional model.
2. Description of Prior Art
Three dimensional ("3-D") graphic models have become increasingly popular since the advent of 3-D laser scanning systems and the boom of VRML (Virtual Reality Modeling Language) models. Laser scanning systems, for example, routinely produce geometric models with hundreds of thousands of vertices and triangles, each of which may contain additional information such as color and normal. Highly detailed models are also commonly adopted in computer graphics.
Three dimensional graphic models are often represented as complex polyhedral meshes composed of two types of data, i.e., topological and geometrical data. Topological data provide connectivity information among vertices (e.g., adjacency of vertices, edges and faces) while geometrical attributes describe the position, normal, color, and application dependent information for each individual vertex. In terms of implementation, most 3-D graphic file formats consist of a list of polygons each of which is specified by its vertex indices and a vertex attribute list. The terms vertex and node are used interchangeably herein.
Generally speaking, 3-D models are expensive to render, awkward to edit, and costly to transmit through a network. Wider application of 3-D graphics potentially could be limited due to these obstacles. To reduce storage requirements and transmission bandwidth it is desirable to compress these models with lossy compression methods which keep the distortion within a tolerable level while maximizing data reduction. Another important consideration is to apply graphic coding in a progressive fashion to allow easier control of data such as progressive display, level-of-detail control and multi-scale editing. This functionality demands that the mesh be approximated with different resolutions, which is vital for real-time applications. To achieve this goal, it is required for the mesh to be reduced to a coarse approximation (i.e. the base mesh) through a sequence of graphic simplifications.
Simplification and compression of 3-D mesh data has been studied by quite a few researchers. Most early work focused on the simplification of graphic models. In W. J. Schroeder, "Decimation of Triangle Meshes," Computer Graphics Proceedings, Annual Conference Series, pp. 65-70, ACM SIGGRAPH, July 1992, the author proposed a decimation algorithm that significantly reduced the number of polygons required to represent an object. Turk, in "Re-tiling Polygon Surfaces," Computer Graphics Proceedings, Annual Conference Series, pp. 55-64, ACM SIGGRAPH, July 1992, presented an automatic method of creating surface models at several levels of detail from an original polyhedral description of a given object. Hoppe et al., in "Mesh Optimization," Computer Graphics Proceedings, Annual Conference Series, pp. 19-26, ACM SIGGRAPH, August 1992, address the mesh optimization problem of approximating a given point set by using smaller number of vertices under certain topological constraints.
Recent work has emphasized the compression of graphic models. Deering, in "Geometry Compression," Computer Graphics Proceedings, Annual Conference Series, pp. 13-20, ACM SIGGRAPH, August 1995, discusses the concept of the generalized triangle mesh which compresses a triangle mesh structure. Eck et al. in "Multiresolution Analysis of Arbitrary Meshes," propose a wavelet transformation defined on an arbitrary domain to compress 3-D models of subdivision connectivity. Taubin, in "Geometric Compression Through Topological Surgery," Tech. Rep. RC-20340, IBM Watson Research Center, January 1996, presented a topological surgery algorithm which utilized two interleaving vertex and triangle trees to compress a model. More recently, Cohen et al., in "Simplification Envelopes," Computer Graphics Proceedings, Annual Conference Series, pp. 119-28, ACM SIGGRAPH, August 1996, introduced the concept of simplification envelopes so that a hierarchy of level-of detail approximations for a given polyhedral model could be generated automatically. Hoppe in "Progressive Meshes," Computer Graphics Proceedings, Annual Conference Series, pp. 99-108, ACM SIGGRAPH, August 1996, proposed a progressive mesh compression algorithm that is applicable to arbitrary meshes.